1. Field of the Invention
The present invention relates generally to communication networks, and more specifically, to the discovery of routes used by data transmitted over such networks.
2. Description of Related Art
Availability of low cost computers, high speed networking products, and readily available network connections has helped fuel proliferation of the Internet. This proliferation has caused the Internet to become an essential tool for both the business community and private individuals. Dependence on the Internet arises, in part, because the Internet makes it possible for multitudes of users to access vast amounts of information and perform remote transactions expeditiously and efficiently. Along with the rapid growth of the Internet have come problems caused by malicious individuals or pranksters launching attacks from within the network. As the size of the Internet continues to grow, so does the threat posed by these individuals.
The ever-increasing number of computers, routers and connections making up the Internet increases the number of vulnerability points from which these malicious individuals can launch attacks. These attacks can be focused on the Internet as a whole or on specific devices, such as hosts or computers, connected to the network. In fact, each router, switch, or computer connected to the Internet may be a potential entry point from which a malicious individual can launch an attack while remaining largely undetected. Attacks carried out on the Internet often consist of malicious packets being injected into the network. Malicious packets can be injected directly into the network by a computer, or a device attached to the network, such as a router or switch, can be compromised and configured to place malicious packets onto the network.
In spite of the development of many sophisticated defense mechanisms such as intrusion detection systems and firewalls, such malicious attacks continue to increase. This is due in part because of a perceived lack of accountability: the anonymous nature of the Internet and its protocols makes it difficult to accurately identify the source of a network attack when the perpetrator wishes to conceal it. In fact, an attacker can generate attacks that appear to have originated from anywhere or nowhere.
There are several reasons why computer networks, especially the Internet, are particularly prone to attacks. First, since networks facilitate remote operations, an attacker may be physically separated from the target. This separation provides some degree of protection. Second, the design of the Internet emphasizes fault tolerance, efficiency, and usefulness over accountability. The legitimacy of IP source addresses is not universally enforced. Routing algorithms are purposefully stateless to facilitate rapid recovery or rerouting of traffic after failure. Login identifiers also hide identity; rather than being the true name of the individual, it is a handle without a strong binding to any real identifying properties at all. In fact, the lack of a strong binding of user to individual is a universal problem, and techniques like PKI (public key infrastructure) seek to make identity and authentication based on identity an integral part of the network. So far such efforts have failed to achieve traction.
Finally, the sociological aspects of the Internet support the establishment and maintenance of loosely coordinated subcultures, complete with group dynamics and peer pressures, some of which reward daring feats. From chat rooms to hacker and cracker communities, individuals say and do things they may never attempt off-line because they have created an alter-ego for their presence on-line, where real names and identities are not being revealed.
Anonymity is a liberating differentiator; inhibitions are relaxed when the fear of being identified is reduced or removed. This is true for most social situations, but more nefariously, anonymity emboldens individuals with ill intentions to act in destructive ways. Often, network-based attacks are perpetrated by individuals seeking to hide their identities. One of the simplest ways to remain anonymous is to hide the source of an attack by chaining together multiple connections into an extended connection. This is typically done by logging into a remote host, then from there logging into a third and fourth and so on until, at the final host, an attack is launched. These intermediate hosts are often referred to as “stepping stones”. Tracing such an attack back to the original source is difficult. Some techniques exist to trace individual connections. However, tracing an extended connection requires identifying related connection pairs at each stepping stone.
The attribution problem can be divided into two parts: (1) finding the source of a flow of attack packets, called the IP Traceback Problem, and (2) discovering which sources are acting to launder the attack, called the Stepping Stone Problem. Consequently, three types of attack sources may be identified: an originating source, stepping stones, and immediate sources. The originating source of an attack, also referred to as the attack source, is the point of origin from which the attacker injects traffic into the network. In the presence of an extended connection, the originating source is the host that initiates the first connection in the connection chain. Stepping stones include intermediate hosts (or routers acting as hosts) along the traversed path of an attack that are exploited to conceal the originating source. The immediate source is the actual host to issue a packet and is also referred to as the packet source. The immediate host may be either the originating source or an intermediate stepping stone. The ability to identify the immediate source of packets is a necessary first step in identifying the originating source of an attack. Yet identifying a packet's source is complicated by both legitimate actions taken upon the packet by the routers as well as the always-present possibility of malicious actors along the packet's path.
There remains a need in the art for effective and efficient methods and systems for performing IP traceback and stepping stone detection so as to accurately attribute network attacks.